package LearnDataStructure.a_线性结构.队列;

import LearnDataStructure.a_线性结构.列表.MyList;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-04 10:38
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.a_线性结构.栈
 */
public class MyLinkedListDouble<T> implements MyList<T> {
    QueueNode<T> head = new QueueNode<T>();
    QueueNode<T> tail = new QueueNode<T>();
    QueueNode<T> now = head;
    int size = 0;

    public MyLinkedListDouble() {
        head.next = tail;
        tail.pre = head;
    }

    @Override
    public void add(T element) {
        QueueNode<T> newNode = new QueueNode<T>(element);//新节点

        tail.pre.next = newNode;//尾部前一个节点A 的 后继是 新节点
        newNode.next = tail;//新节点的后继是尾部
        newNode.pre = tail.pre;//新节点的前驱是A
        tail.pre = newNode;//尾部的前驱是新节点

        size++;
    }

    @Override
    public void delete(T element) {
        if (head.next == tail) {
            return;
        }
        QueueNode<T> p = head.next;
        while (p != tail) {
            if (p.data.equals(element)) {
                p.pre.next = p.next;
                p.next.pre = p.pre;
                p.pre = null;
                p.next = null;
                size--;
                break;
            }
            p = p.next;
        }
    }

    @Override
    public void delete(int index) {
        if (index < 0 || index >= size || head.next == tail) {
            return;
        }
        int i = 0;
        QueueNode<T> p = head.next;
        while (p != tail) {
            if (i == index) {
                p.pre.next = p.next;
                p.next.pre = p.pre;
                p.pre = null;
                p.next = null;
                size--;
                break;
            }
            p = p.next;
            i++;
        }
    }

    @Override
    public void update(int index, T newElement) {
        if (index < 0 || index >= size || head.next == tail) {
            return;
        }
        int i = 0;
        QueueNode<T> p = head.next;
        while (p != tail) {
            if (i == index) {
                p.data = newElement;
                break;
            }
            p = p.next;
            i++;
        }
    }

    @Override
    public boolean contains(T target) {
        if (head.next != tail) {
            QueueNode<T> p = head.next;
            while (p != tail) {
                if (p.data.equals(target)) {
                    return true;
                }
                p = p.next;
            }
        }
        return false;
    }

    @Override
    public T AtElement(int index) {
        if (index < 0 || index >= size || head.next == tail) {
            return null;
        }
        int i = 0;
        QueueNode<T> p = head.next;
        while (p != tail) {
            if (i == index) {
                return p.data;
            }
            p = p.next;
            i++;
        }
        return null;
    }

    @Override
    public int indexOf(T element) {
        if (head.next != tail) {
            int i = 0;
            QueueNode<T> p = head.next;
            while (p != tail) {
                if (p.data.equals(element)) {
                    return i;
                }
                p = p.next;
                i++;
            }
        }
        return -1;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder("[");
        QueueNode<T> p = head.next;
        while (p != tail) {
            stringBuilder.append(p.data);
            if (p.next != tail) {
                stringBuilder.append(" , ");
            }
            p = p.next;
        }
        stringBuilder.append("] size = " + size);
        return stringBuilder.toString();
    }

    /**
     * 此元素后面是否还有元素
     * @return
     */
    @Override
    public boolean hasNext() {
        return now.next != tail;
    }

    /**
     * 返回从head开始的，下一个元素A，到tail前一个元素B为止
     * @return
     */
    @Override
    public T next() {
        QueueNode<T> next = now.next;
        now = now.next;
        return next.data;
    }
}

